package 链表;

/**
 * 删除链表中等于给定值 val 的所有节点。
 * <p>
 * 示例:
 * 输入: 1->2->6->3->4->5->6, val = 6
 * 输出: 1->2->3->4->5
 * <p>
 * https://leetcode-cn.com/problems/remove-linked-list-elements/
 */
public class _203_移除链表元素 {

    public static void main(String[] args) {
        ListNode first = new ListNode(11);
        ListNode second = new ListNode(11);
        ListNode third = new ListNode(13);
        ListNode four = new ListNode(12);
        ListNode five = new ListNode(11);
        first.next = second;
        second.next = third;
        third.next = four;
        four.next = five;
        LinkedListUtils.printNode(first);
        ListNode node = removeElements(first, 11);
        LinkedListUtils.printNode(node);
    }

    /**
     * 先确定头节点，然后遍历删除为值的节点
     */
    public static ListNode removeElements(ListNode head, int val) {
        // 代表就head一个节点,而且值为给定要删除的值
        if ((head == null)) {
            return null;
        }
        // 先把头节点的值删掉
        while (head.val == val) {
            if (head.next == null) {
                return null;
            } else {
                head = head.next;
            }
        }

        // 记录下一个节点
        ListNode prev = head;
        ListNode next = head.next;
        while (next != null) {
            if (next.val == val) {
                prev.next = next.next;
            } else {
                prev = next;
            }
            next = next.next;
        }
        return head;
    }

    /**
     * 低内存, 更优解法
     */
    public static ListNode removeElements2(ListNode head, int val) {
        // 使用哑结点
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode pre = sentinel, cur = head;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        return sentinel.next;
    }
}
